#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1.5e5+5;
int n,m,q,qf[maxn],fl,fr;
ll a[maxn],b[maxn],c[maxn],ans;
int main()
{
    int l,r;
    freopen("clear.in","r",stdin);
    freopen("clear.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    while(q--)
    {
        cin>>l>>r;
        for(int i=0;i<=r-l;i++) b[i+1]=a[i+l];
        b[r-l+2]=0;
        for(int i=1;i<=r-l+2;i++) c[i]=b[i]-b[i-1];
        fl=1,fr=0,ans=0;
        for(int i=1;i<=min(m,r-l+2);i++) if(c[i]<0) qf[++fr]=i;
        for(int i=1;i<=r-l+2;i++)
        {
            if(i+m<=r-l+2 && c[i+m]<0) qf[++fr]=i+m;
            ans+=c[i];
            while(fl<=fr && c[i]>0)
            {
                if(c[i]+c[qf[fl]]>=0)
                {
                    c[i]+=c[qf[fl]];
                    c[qf[fl]]=0;
                    fl++;
                }
                else
                {
                    c[qf[fl]]+=c[i];
                    c[i]=0;
                }
            }
            c[min(r-l+2,i+m)]+=c[i];
            c[i]=0;
        }
        cout<<ans<<'\n';
    }
    return 0;
}
